package demoExercise;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-10-27
 * Time: 0:56
 */

//地下城游戏
public class Demo2 {

    public int calculateMinimumHP(int[][] dungeon) {

        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];

        //初始化
        for(int j = 0; j <= n; j++) dp[m][j] = Integer.MAX_VALUE;
        for(int j = 0; j <= m; j++) dp[j][n] = Integer.MAX_VALUE;

        dp[m][n-1] = dp[m-1][n] = 1;

        //填表
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >= 0; j--){
                dp[i][j] = Math.min(dp[i][j+1],dp[i+1][j]) - dungeon[i][j];
                dp[i][j] = Math.max(dp[i][j],1);
            }
        }

        return dp[0][0];
    }
}
